{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest Impossible Sequence of Rolls"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shortestSequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不可能得到的最短骰子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code>&nbsp;的整数数组&nbsp;<code>rolls</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;。你扔一个&nbsp;<code>k</code>&nbsp;面的骰子 <code>n</code>&nbsp;次，骰子的每个面分别是&nbsp;<code>1</code>&nbsp;到&nbsp;<code>k</code>&nbsp;，其中第&nbsp;<code>i</code>&nbsp;次扔得到的数字是&nbsp;<code>rolls[i]</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回 <strong>无法</strong>&nbsp;从 <code>rolls</code>&nbsp;中得到的 <strong>最短</strong>&nbsp;骰子子序列的长度。</p>\n",
    "\n",
    "<p>扔一个 <code>k</code>&nbsp;面的骰子 <code>len</code>&nbsp;次得到的是一个长度为 <code>len</code>&nbsp;的 <strong>骰子子序列</strong>&nbsp;。</p>\n",
    "\n",
    "<p><strong>注意</strong>&nbsp;，子序列只需要保持在原数组中的顺序，不需要连续。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>rolls = [4,2,1,2,3,3,2,4,1], k = 4\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>所有长度为 1 的骰子子序列 [1] ，[2] ，[3] ，[4] 都可以从原数组中得到。\n",
    "所有长度为 2 的骰子子序列 [1, 1] ，[1, 2] ，... ，[4, 4] 都可以从原数组中得到。\n",
    "子序列 [1, 4, 2] 无法从原数组中得到，所以我们返回 3 。\n",
    "还有别的子序列也无法从原数组中得到。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>rolls = [1,1,2,2], k = 2\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>所有长度为 1 的子序列 [1] ，[2] 都可以从原数组中得到。\n",
    "子序列 [2, 1] 无法从原数组中得到，所以我们返回 2 。\n",
    "还有别的子序列也无法从原数组中得到，但 [2, 1] 是最短的子序列。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>rolls = [1,1,3,2,2,2,3,3], k = 4\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>子序列 [4] 无法从原数组中得到，所以我们返回 1 。\n",
    "还有别的子序列也无法从原数组中得到，但 [4] 是最短的子序列。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == rolls.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= rolls[i] &lt;= k &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-impossible-sequence-of-rolls](https://leetcode.cn/problems/shortest-impossible-sequence-of-rolls/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-impossible-sequence-of-rolls](https://leetcode.cn/problems/shortest-impossible-sequence-of-rolls/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,1,2,3,3,2,4,1]\\n4', '[1,1,2,2]\\n2', '[1,1,3,2,2,2,3,3]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        visit = 0\n",
    "        count = 0\n",
    "        for e in rolls:\n",
    "            visit |= (1 << e)\n",
    "            if visit == (1 << k+1)-2:\n",
    "                count += 1\n",
    "                visit = 0\n",
    "        return count+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        \n",
    "        # 贪心\n",
    "        mark = [0] * (k + 1) # mark[v] 标记v属于哪个子段\n",
    "        ans, left = 1, k\n",
    "        for v in rolls:\n",
    "            if mark[v] < ans:\n",
    "                mark[v] = ans\n",
    "                left -= 1\n",
    "                if left == 0:\n",
    "                    left = k\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        mark = [0] * (k + 1)\n",
    "        ans,left = 1,k\n",
    "        for v in rolls:\n",
    "            if mark[v] < ans:\n",
    "                mark[v] = ans\n",
    "                left -= 1\n",
    "                if left == 0:\n",
    "                    left = k\n",
    "                    ans += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        ans=0\n",
    "        T=(1<<(k+1))-2\n",
    "        cur=0\n",
    "        for r in rolls:\n",
    "            cur |=1<<r\n",
    "            if cur==T:\n",
    "                cur=0\n",
    "                ans+=1\n",
    "        return ans+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        ret = 1\n",
    "\n",
    "        vis = [0]*(k+1)\n",
    "        left = k\n",
    "\n",
    "        for roll in rolls:\n",
    "            if vis[roll] >= ret:\n",
    "                continue\n",
    "            vis[roll] = ret\n",
    "            left -= 1\n",
    "            if left == 0:\n",
    "                ret += 1\n",
    "                left = k\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        lst = [False]*k\n",
    "        cnt = 0\n",
    "        res = 1\n",
    "        \n",
    "        for v in rolls:\n",
    "            if not lst[v-1]:\n",
    "                lst[v-1] = True\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    lst = [False]*k\n",
    "                    cnt = 0\n",
    "                    res += 1\n",
    "        return res\t\t\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        mark_order = [0] * (k+1) #每个元素储存在第几个 1 到 k 的最短子串\n",
    "        res = 0\n",
    "        left = k #判断已经有几个数字被记录 \n",
    "        for roll in rolls:\n",
    "            if(mark_order[roll] == res):\n",
    "                mark_order[roll] += 1\n",
    "                left -= 1\n",
    "            if(left == 0):\n",
    "                res += 1\n",
    "                left = k\n",
    "        \n",
    "        return res + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        # 因为判断某个序列是不是给定数组的子序列的过程是个从前往后贪心匹配的过程，所以构造一个不在其中的序列的过程可以看成是在匹配过程中不停反悔的过程，只要能不匹配就不匹配，直到所有可用的字母都被否定过之后才被迫承认匹配上了一个字符，这样就得到了O(n)的解法。\n",
    "        # 构造一个最短的，不在rolls中的子序列\n",
    "        # 匹配一定是从第一个开始，所以出现的晚的好 \n",
    "        # 遍历rolls，找到一个完整的段包含1-k，取最后一个出现的数字，第几段，长度尝试+1\n",
    "                                                # 这个最后的数字在当前段只出现过一次\n",
    "        mark = [0]*(k+1)\n",
    "        ans, left = 1, k#当前子序列长ans, 剩余未出现的数字有k个\n",
    "        for v in rolls:\n",
    "            # print(mark)\n",
    "            if mark[v]<ans: # v已出现的段 mark[v]段，第ans段还没有\n",
    "                mark[v] = ans # 在ans段出现了一个新的数\n",
    "                left -=1 # 当前段剩余未出现的数少一个\n",
    "                if left ==0:# 这个长度的子序列全都有的\n",
    "                    left = k # 清空，记录下一段\n",
    "                    ans += 1 # 进入下一段的计数\n",
    "            # print(ans)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        lst = [0] * (k + 1)\n",
    "        count = 0\n",
    "        res = 1\n",
    "        for v in rolls:\n",
    "            if lst[v] < res:\n",
    "                lst[v] = res\n",
    "                count += 1\n",
    "\n",
    "            if count == k:\n",
    "                res+=1\n",
    "                count = 0\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        mark = [0] * (k + 1)\n",
    "        ans, left = 1, k\n",
    "        for v in rolls:\n",
    "            if mark[v] < ans:\n",
    "                mark[v] = ans\n",
    "                left -= 1\n",
    "                if left == 0:\n",
    "                    ans += 1\n",
    "                    left = k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        lst = [False]*k\n",
    "        cnt = 0\n",
    "        res = 1\n",
    "        \n",
    "        for v in rolls:\n",
    "            if not lst[v-1]:\n",
    "                lst[v-1] = True\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    lst = [False]*k\n",
    "                    cnt = 0\n",
    "                    res += 1\n",
    "        return res\t\t\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        mark = [0] * (k + 1)  # mark[v] 标记 v 属于哪个子段\n",
    "        ans, left = 1, k\n",
    "        for v in rolls:\n",
    "            if mark[v] < ans:\n",
    "                mark[v] = ans\n",
    "                left -= 1\n",
    "                if left == 0:\n",
    "                    left = k\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        n = len(rolls)\n",
    "        ans = 1\n",
    "        cnt = 0\n",
    "        found = [False] * (k+1)\n",
    "        for x in rolls:\n",
    "            if not found[x]:\n",
    "                found[x] = True\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    ans += 1\n",
    "                    cnt = 0\n",
    "                    found = [False] * (k+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        lst = [0]*k\n",
    "        cnt = 0\n",
    "        res = 1\n",
    "        for v in rolls:\n",
    "            if lst[v-1] < res :\n",
    "                lst[v-1]  = res\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    cnt = 0\n",
    "                    res += 1\n",
    "        return res\t\t\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        appears = [0]*(k+1)\n",
    "        appeared = runs = 0\n",
    "        for n in rolls:\n",
    "            if appears[n]: continue\n",
    "            appeared += 1\n",
    "            if appeared == k:\n",
    "                appeared = 0\n",
    "                for i in range(1, k+1):\n",
    "                    appears[i] = 0\n",
    "                runs += 1\n",
    "            else:\n",
    "                appears[n] = 1\n",
    "        return runs + 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        m = [0] * (k + 1)\n",
    "        re, cnt = 1, k\n",
    "        for x in rolls:\n",
    "            if m[x] < re:\n",
    "                m[x] = re\n",
    "                cnt -= 1\n",
    "                if (cnt == 0):\n",
    "                    re += 1\n",
    "                    cnt = k\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        mark = [0] * (k + 1)  # mark[v] 标记 v 属于哪个子段\n",
    "        ans, left = 1, k\n",
    "        for v in rolls:\n",
    "            if mark[v] < ans:\n",
    "                mark[v] = ans\n",
    "                left -= 1\n",
    "                if left == 0:\n",
    "                    left = k\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        mark = [0] * (k + 1)  # mark[v] 标记 v 属于哪个子段\n",
    "        ans, left = 1, k\n",
    "        for v in rolls:\n",
    "            if mark[v] < ans:\n",
    "                mark[v] = ans\n",
    "                left -= 1\n",
    "                if left == 0:\n",
    "                    left = k\n",
    "                    ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        lst = [0]*k\n",
    "        cnt = 0\n",
    "        res = 1\n",
    "        \n",
    "        for v in rolls:\n",
    "            if lst[v-1] < res :\n",
    "                lst[v-1] += 1\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    cnt = 0\n",
    "                    res += 1\n",
    "        return res\t\t\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegTreeMin:\n",
    "    def __init__(self, n):\n",
    "        self.nums = [0] * (4*n)\n",
    "\n",
    "    # 某个结点的标号node，区间左侧left，区间右侧right，添加的位置idx，添加的值val\n",
    "    def set(self, node, left, right, idx, val):\n",
    "        if left == right:\n",
    "            self.nums[node] = val\n",
    "            return\n",
    "        mid = (right + left) // 2\n",
    "        if idx <= mid:\n",
    "            self.set(2 * node + 1, left, mid, idx, val)\n",
    "        else:\n",
    "            self.set(2 * node + 2, mid + 1, right, idx, val)\n",
    "        self.nums[node] = min(self.nums[2*node+1], self.nums[2*node+2])\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        # 首先，如果能得到更长的序列，所以短的一定能覆盖，是具备单调性的\n",
    "        tree = SegTreeMin(k)\n",
    "        for x in rolls[::-1]:\n",
    "            minval = tree.nums[0]\n",
    "            tree.set(node=0, left=0, right=k-1, idx=x-1, val=minval+1)\n",
    "        return 1 + tree.nums[0]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1 \n",
    "        s = set()\n",
    "        for x in rolls:\n",
    "            s.add(x)\n",
    "            if len(s) == k:\n",
    "                res += 1 \n",
    "                s.clear()\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        # lst = [1]*k\n",
    "        # count1 = 1\n",
    "        # for v in rolls:\n",
    "        #     if lst[v-1] == 1:\n",
    "        #         lst[v-1] = 0\n",
    "        #     if 1 not in lst:\n",
    "        #         lst = [1]*k\n",
    "        #         count1 += 1\n",
    "        # return count1\n",
    "        lst = set()\n",
    "        count1 = 1\n",
    "        for v in rolls:\n",
    "            lst.add(v)\n",
    "            if len(lst) == k:\n",
    "                lst = set()\n",
    "                count1 += 1\n",
    "        return count1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        # 考虑成能找到多少组 (1~k)的段\n",
    "        s = set()\n",
    "        ans = 0\n",
    "        for r in rolls:\n",
    "            s.add(r)\n",
    "            if len(s) == k:\n",
    "                ans += 1\n",
    "                s.clear()\n",
    "        return ans + 1 # 找到ans个段,可以随意构建ans长度的序列,但ans + 1长度就不行了"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        s=set()\n",
    "        ans=0\n",
    "        for r in rolls:\n",
    "            s.add(r)\n",
    "            if len(s)==k:\n",
    "                s.clear()\n",
    "                ans+=1\n",
    "        return ans+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        tmp = set()\n",
    "        for v in rolls:\n",
    "            tmp.add(v)\n",
    "            if len(tmp) == k:\n",
    "                res += 1\n",
    "                tmp = set()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        set1 = set()\n",
    "        for v in rolls:\n",
    "            set1.add(v)\n",
    "            if len(set1) == k:\n",
    "                res += 1\n",
    "                set1.clear()\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        st = set()\n",
    "        res = 1\n",
    "        for v in rolls:\n",
    "            if v not in st:\n",
    "                st.add(v)\n",
    "            if len(st) == k:\n",
    "                res += 1\n",
    "                st.clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        ans = 1\n",
    "        s = set()\n",
    "        for x in rolls:\n",
    "            if x not in s:\n",
    "                s.add(x)\n",
    "                if len(s) == k:\n",
    "                    s = set()\n",
    "                    ans += 1\n",
    "        return ans\n",
    "        # mark = [0] * (k + 1)\n",
    "        # ans,left = 1,k\n",
    "        # for v in rolls:\n",
    "        #     if mark[v] < ans:\n",
    "        #         mark[v] = ans\n",
    "        #         left -= 1\n",
    "        #         if left == 0:\n",
    "        #             left = k\n",
    "        #             ans += 1\n",
    "        # return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        tmp = set()\n",
    "        for v in rolls:\n",
    "            tmp.add(v)\n",
    "            if len(tmp) == k:\n",
    "                res += 1\n",
    "                tmp = set()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        dic = set()\n",
    "        ans = 1\n",
    "        for i in range(len(rolls)):\n",
    "            if(rolls[i] not in dic):\n",
    "                dic.add(rolls[i])\n",
    "                if(len(dic) == k):\n",
    "                    ans += 1\n",
    "                    dic = set()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        st = set()\n",
    "        res = 1\n",
    "        for v in rolls:\n",
    "            if v not in st:\n",
    "                st.add(v)\n",
    "            if len(st) == k:\n",
    "                res += 1\n",
    "                st = set()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        dic = set()\n",
    "        ans = 0\n",
    "        for i in range(len(rolls)):\n",
    "            if(rolls[i] not in dic):\n",
    "                dic.add(rolls[i])\n",
    "                if(len(dic) == k):\n",
    "                    ans += 1\n",
    "                    dic = set()\n",
    "        return ans+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        s = set()\n",
    "        ans = 1\n",
    "        for x in rolls:\n",
    "            if x not in s:\n",
    "                s.add(x)\n",
    "                if len(s) == k:\n",
    "                    s = set()\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        tmp = set()\n",
    "        for v in rolls:\n",
    "            tmp.add(v)\n",
    "            if len(tmp) == k:\n",
    "                res += 1\n",
    "                tmp = set()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        st = set()\n",
    "        ret = 0\n",
    "        for x in rolls:\n",
    "            st.add(x)\n",
    "            if len(st) == k:\n",
    "                ret += 1\n",
    "                st.clear()\n",
    "        return ret + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        ans = 1\n",
    "        pre = set()\n",
    "        for num in rolls:\n",
    "            pre.add(num)\n",
    "            if len(pre) == k:\n",
    "                ans += 1\n",
    "                pre = set()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        set1 = set()\n",
    "        for v in rolls:\n",
    "            if v <= k:\n",
    "                set1.add(v)\n",
    "            if len(set1) == k:\n",
    "                res += 1\n",
    "                set1.clear()\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        ans = 1\n",
    "        s = set()\n",
    "        for x in rolls:\n",
    "            s.add(x)\n",
    "            if len(s) == k:\n",
    "                ans += 1\n",
    "                s.clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        set1 = set()\n",
    "        for v in rolls:\n",
    "            if v <= k:\n",
    "                set1.add(v)\n",
    "            if len(set1) == k:\n",
    "                res += 1\n",
    "                set1.clear()\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        s = set()\n",
    "        ret = 1\n",
    "        for x in rolls:\n",
    "            s.add(x)\n",
    "            if len(s) == k:\n",
    "                ret += 1\n",
    "                s = set()\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        tmp = set()\n",
    "        for v in rolls:\n",
    "            tmp.add(v)\n",
    "            if len(tmp) == k:\n",
    "                res += 1\n",
    "                tmp = set()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        st = set()\n",
    "        res = 1\n",
    "        for v in rolls:\n",
    "            if v not in st:\n",
    "                st.add(v)\n",
    "            if len(st) == k:\n",
    "                res += 1\n",
    "                st = set()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        s = set()\n",
    "        ans = 1\n",
    "        for x in rolls:\n",
    "            s.add(x)\n",
    "            if len(s) == k:\n",
    "                ans += 1\n",
    "                s.clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "\n",
    "        st = set()\n",
    "        ans = 0 #ans表示能得到所有长度为ans的子序列\n",
    "        for r in rolls:\n",
    "            st.add(r)\n",
    "            if len(st)==k: #这组的数字全了，清空哈希集合，进入下一组\n",
    "                st.clear()\n",
    "                ans+=1\n",
    "        return ans+1 #ans+1就无法保证了\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        n = len(rolls)\n",
    "\n",
    "        i = 0\n",
    "        s = set()\n",
    "        ans = 0\n",
    "        while i < n:\n",
    "            s.add(rolls[i])\n",
    "            if len(s) == k:\n",
    "                ans += 1\n",
    "                s = set()\n",
    "            i += 1\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        tmp = set()\n",
    "        count = 0\n",
    "        for v in rolls:\n",
    "            tmp.add(v)\n",
    "            count +=1\n",
    "            if len(tmp) == k:\n",
    "                res += 1\n",
    "                tmp = set()\n",
    "                count = 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "\n",
    "        cnt = 0\n",
    "\n",
    "        vis = set()\n",
    "        for r in rolls:\n",
    "            vis.add(r)\n",
    "            if len(vis) == k:\n",
    "                cnt += 1\n",
    "                vis = set()\n",
    "        return cnt + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        set1 = set()\n",
    "        for i in range(len(rolls)):\n",
    "            if rolls[i] <= k:\n",
    "                set1.add(rolls[i])\n",
    "            if len(set1) == k:\n",
    "                res += 1\n",
    "                set1.clear()\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "  \n",
    "        s = set()\n",
    "        count = 1\n",
    "        for v in rolls:\n",
    "            if v not in s:\n",
    "                s.add(v)\n",
    "            if len(s) == k:\n",
    "                count += 1\n",
    "                s = set()\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        set1 = set()\n",
    "        for i in range(len(rolls)):\n",
    "            if rolls[i] <= k:\n",
    "                set1.add(rolls[i])\n",
    "            if len(set1) == k:\n",
    "                res += 1\n",
    "                set1 = set()\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls, k):\n",
    "        res=0\n",
    "        kset=set()\n",
    "        for i in rolls:\n",
    "            kset.add(i)\n",
    "            if len(kset)==k:\n",
    "                res+=1\n",
    "                kset=set()\n",
    "        return res+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        set1 = set()\n",
    "        for i in range(len(rolls)):\n",
    "            if rolls[i] <= k:\n",
    "                set1.add(rolls[i])\n",
    "            if len(set1) == k:\n",
    "                res += 1\n",
    "                set1.clear()\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls, k):\n",
    "        res=0\n",
    "        kset=set()\n",
    "        for i in rolls:\n",
    "            kset.add(i)\n",
    "            if len(kset)==k:\n",
    "                res+=1\n",
    "                kset=set()\n",
    "        return res+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        set1 = set()\n",
    "        for i in range(len(rolls)):\n",
    "            if rolls[i] <= k:\n",
    "                set1.add(rolls[i])\n",
    "            if len(set1) == k:\n",
    "                res += 1\n",
    "                set1 = set()\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        set_ = set()\n",
    "        for v in rolls:\n",
    "            set_.add(v)\n",
    "            if len(set_) == k:\n",
    "                res += 1\n",
    "                set_ = set()\n",
    "        return res + 1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
